package com.zyk.grate_offer.class04;

/**
 * 力扣： https://leetcode-cn.com/problems/candy/
 *
 * @author zhangsan
 * @date 2021/4/28 17:13
 */
public class Code05_Candy {

    // 思路, 一个上坡路, 一个下坡路, 遇到小于当前,或者等于当前. 都从1颗重新分起
    // 左右两边求最大值,是该孩子最少符合要求分配的糖.
    public static int candy(int[] ratings) {
        int N = ratings.length;
        int[] left = new int[N];
        int[] right = new int[N];
        left[0] = 1;
        right[N - 1] = 1;

        for (int i = 1; i < N; i++) {
            left[i] = ratings[i] > ratings[i - 1] ? left[i - 1] + 1 : 1;
        }

        for (int i = N - 2; i >= 0; i--) {
            right[i] = ratings[i] > ratings[i + 1] ? right[i + 1] + 1 : 1;
        }

        int ans = 0;
        for (int i = 0; i < N; i++) {
            ans += Math.max(left[i], right[i]);
        }

        return ans;
    }


    // for test
    public static void main(String[] args) {
        int[] ratings = {1, 2, 2};
        System.out.println(candy(ratings));
    }

}
